\documentclass[10pt]{article}
\usepackage{amsmath}
\usepackage{graphicx}

\newcommand{\problem}[1]{\noindent{\sc Problem #1.}}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\complexity}{\noindent{\sc Complexity. }}
\newcommand{\answer}{\noindent{\sc Answer. }}
\newcommand{\given}{\,|\,}
\newcommand{\divides}{\,|\,}

\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}

\problem{232}
The Race.

Two players share an unbiased coin and take it in turns to play \emph{The Race}. On Player 1's turn, he tosses the coin once: if it comes up Heads, he scores one point; if it comes up Tails, he scores nothing. On Player 2's turn, she chooses a positive integer $T$ and tosses the coin $T$ times: if it comes up all Heads, she scores $2^{T-1}$ points; otherwise, she scores nothing. Player 1 goes first. The winner is the first to 100 or more points.

On each turn Player 2 selects the number, $T$, of coin tosses that maximizes the probability of her winning.

What is the probability that Player 2 wins?

Give your answer rounded to eight decimal places in the form 0.abcdefgh .

\solution

Let $N$ denote the number of heads to win the game. Let $p(a,b)$ be the probability that player 2 wins the game when it's player 1's turn. Let $q(a,b)$ be the probability that player 2 wins the game when it's player 2's turn. Since player 1 always tosses the coin once, it's straightforward that
\[
p(a,b) = \frac12 q(a+1,b) + \frac12 q(a,b)
\]
if $a,b < N$, and special cases $p(N+, b)=0$, $p(a,N+)=1$.

Now for player B's decision, it satisfies
\[
q(a,b) = \max \left\{ \frac{1}{2^k} \, p(a,b+2^{k-1}) + \left(1-\frac{1}{2^k}\right) p(a,b) \right\}
\]
We find the solution by solving each equation in turn and find the largest $q$. If $b+2^{k-1}<N$, the solution is
\[
q(a,b) = \frac{ q(a+1,b+2^{k-1}) + q(a,b+2^{k-1}) + (2^k-1)q(a+1,b) }{2^k+1}
\]
If $b+2^{k-1} \ge N$, the solution is
\[
q(a,b) = \frac{ 2 + (2^k-1)q(a+1,b) }{2^k+1}
\]
We note that this case can be treated as a special case of the first one by letting $q(a,b)=1$ for $b \ge N$.

\answer
0.83648556

\complexity

Time complexity: $\mathcal{O}(N^2 \log N)$

Space complexity: $\mathcal{O}(N^2)$

\end{document}
